import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-08-24
 * Time: 16:41
 */
public class Solution {
    static class TreeNode { int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        if (root == p || root == q) {
            return root;
        }

        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);

        if (leftTree != null && rightTree != null) {
            return root;
        }else if (leftTree != null) {
            return leftTree;
        }else {
            return rightTree;
        }
    }

    //方法二
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        getPath(root,p,stackP);
        getPath(root,q,stackQ);

        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if (sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            while (size != 0) {
                stackP.pop();
                size--;
            }
        }else {
            int size = sizeQ - sizeP;
            while (size != 0) {
                stackQ.pop();
                size--;
            }
        }
        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
            if (stackP.peek() != stackQ.peek()) {
                stackP.pop();
                stackQ.pop();
            }else {
                return stackP.peek();
            }
        }
        return null;
    }
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) return false;
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean left = getPath(root.left,node,stack);
        if (left) {
            return true;
        }
        boolean right = getPath(root.right,node,stack);
        if (right) {
            return true;
        }
        stack.pop();
        return false;
    }
}
